package graph;

import java.util.*;

public class DijkstraArray {

    private static final int MAX_VALUE = Integer.MAX_VALUE;

    public static void main(String[] args) {
        int[][] graph = { { 0, 2, 4, 0, 0, 0 },
                          { 2, 0, 1, 4, 2, 0 },
                          { 4, 1, 0, 0, 3, 0 },
                          { 0, 4, 0, 0, 3, 2 },
                          { 0, 2, 3, 3, 0, 2 },
                          { 0, 0, 0, 2, 2, 0 } };

        int[] shortestDistances = dijkstra(graph, 0);

        System.out.println("Shortest distances from source to all nodes:");
        for (int i = 0; i < shortestDistances.length; i++) {
            System.out.println("Node " + i + ": " + shortestDistances[i]);
        }
    }

    public static int[] dijkstra(int[][] graph, int source) {
        int n = graph.length;

        // 初始化距离数组
        int[] distances = new int[n];
        Arrays.fill(distances, MAX_VALUE);
        distances[source] = 0;

        // 初始化已访问节点集合
        boolean[] visited = new boolean[n];

        // 执行n-1轮迭代
        for (int i = 0; i < n - 1; i++) {
            // 找到未访问节点中距离最小的节点
            int minIndex = -1;
            int minDistance = MAX_VALUE;
            for (int j = 0; j < n; j++) {
                if (!visited[j] && distances[j] < minDistance) {
                    minIndex = j;
                    minDistance = distances[j];
                }
            }

            // 标记该节点为已访问
            visited[minIndex] = true;

            // 更新该节点的邻接节点的距离
            for (int k = 0; k < n; k++) {
                if (graph[minIndex][k] > 0 && distances[minIndex] != MAX_VALUE) {
                    int newDistance = distances[minIndex] + graph[minIndex][k];
                    if (newDistance < distances[k]) {
                        distances[k] = newDistance;
                    }
                }
            }
        }

        return distances;
    }
}
